package ch09_08;

/**
 * Good Question.
 * Need Practice again.
 * Hint: If denom comes down to 1, there is only one way to give changes: all 1 cents.
 * So return ONE directly.
 * @author ryan
 *
 */
public class Solution {
    public static long waysToChange(int[] denom, int amount) {
	if (amount <= 0)
	    return 0;
	return ways(denom, 0, 0, amount);
    }

    private static long ways(int[] denom, int index, int sum, int amount) {
	
	/**
	 * Good Question.
	 * Return value should be larger than 0 at some condition.
	 */
//    	if (sum >= amount) {
    	if (sum > amount) {
    	    return 0;
    	}
    	
    	if (sum == amount) {
    		return 1;
    	}
    	if (index == denom.length) {
    		return 0;
    	}
	int d = denom[index];
	/**
	 * Good Question.
	 * if denom is larger than amount, change to the next smaller denometor.
	 */
	if (d > amount) {
		if (index < denom.length) {
			return ways(denom, index + 1, sum, amount);
		} else {
			return 0;
		}
	}
	long result = 0;
	while (sum <= amount) {
	    result += ways(denom, index + 1, sum, amount);
	    sum += d;
	}
	return result;
    }

    public static void main(String... args) {
	int[] denom = {25, 10, 5, 1};
	int amount = 15;
	long result = waysToChange(denom, amount);
	System.out.println(result);
    }
}